#include "combinationSum.h"
void dfsSum(std::vector<int> &candidates, std::vector<std::vector<int>> &cache,
            std::vector<int> res, int target) {
    if (target < 0)
        return;
    if (target == 0) {
        cache.push_back(res);
    } else {
        for (auto e : candidates) {
            if (res.empty()) {
                res.push_back(e);
                dfsSum(candidates, cache, res, target - e);
                res.pop_back();
            } else {
                if (e >= res.back()) {
                    res.push_back(e);
                    dfsSum(candidates, cache, res, target - e);
                    res.pop_back();
                }
            }
        }
    }
}

std::vector<std::vector<int>> combinationSum(std::vector<int> &candidates,
                                             int target) {
    std::vector<std::vector<int>> cache;
    std::vector<int> res;
    dfsSum(candidates, cache, res, target);
    return cache;
}

void dfsSum2(std::vector<int> &candidates, std::vector<std::vector<int>> &cache,
             std::vector<int> res, int start, int target) {
    if (target == 0) {
        cache.push_back(res);
    } else {
        for (int i = start;
             i < candidates.size() && target - candidates[i] >= 0; i++) {

            if (i > start && candidates[i] == candidates[i - 1])
                continue;
            res.push_back(candidates[i]);
            dfsSum2(candidates, cache, res, i + 1, target - candidates[i]);
            res.pop_back();
        }
    }
}

std::vector<std::vector<int>> combinationSum2(std::vector<int> &candidates,
                                              int target) {
    std::sort(candidates.begin(), candidates.end());
    std::vector<std::vector<int>> cache;
    std::vector<int> res;
    dfsSum2(candidates, cache, res, 0, target);
    return cache;
}
